package leetcode;

/**
 * Created by shuowu on 2018/3/9.
 */
public class RepatedStringMatch {

    // 我写的210ms
    public int myRepeatedStringMatch(String A, String B) {
        if(A == null || B == null || A.length() <= 0 || B.length() <= 0){
            return 0;
        }
        if(A.contains(B)){
            return 1;
        }
        // 核心思想是A 的长度大于等于B之后，先查找一次，如果没有找到，再增加一次A
        // 如果还没有找到，那就是没有了
        int length = B.length();
        int lengthA = A.length();
        int times = (int)Math.ceil((float)length / lengthA);
        StringBuilder temp = new StringBuilder(A);
        for (int i = 1; i < times; i++){
            temp.append(A);
        }
        if(temp.toString().contains(B)){
            return times;
        } else {
            if(temp.append(A).toString().contains(B)){
                return times + 1;
            }
        }
        return -1;
    }

    //4ms sample
    public int repeatedStringMatch(String A, String B) {
        if(B.length()<=A.length()+1) {
            if(A.contains(B)) return 1;
            else {
                String A2 = A+A;
                if(A2.contains(B)) return 2;
            }
            return -1;
        }

        char[] cb = B.toCharArray();
        char[] ca = A.toCharArray();
        int lena=ca.length;
        int lenb=cb.length;
        int start = 0;
        int nrepeat=-1;
        while(start<lenb) {
            if(cb[start]==ca[0]) {
                if(start>=lena) return -1;
                int len=1;
                while(start+len<lenb) {
                    if(cb[start+len]==ca[len%lena]) {
                        len++;
                    }else{
                        return -1;
                    }

                }
                if(len%lena==0) nrepeat=len/lena;
                else nrepeat = 1+len/lena;
                if(start!=0) {

                    int n=1;
                    while(start-n>=0) {
                        if(cb[start-n]!=ca[lena-n]) return -1;
                        n++;
                    }

                    nrepeat++;
                }
                break;
            }
            start++;
        }
        return nrepeat;
    }

    //5ms的sample
    public int repeatedStringMatch2(String A, String B) {
        int ans = 1;
        if (B.isEmpty() || A.equals(B)) return ans;

        int n = A.length();
        int m = B.length();
        char firstB = B.charAt(0);
        int i = 0;
        int j = 0;
        boolean found = true;
        // Check if B is in the middle of A or in the second half of A
        while ((i = A.indexOf(firstB, i)) != -1) {
            found = true;
            for (j = 0; j < m && i + j < n; j++) {
                // In the middle?
                if (A.charAt(i + j) != B.charAt(j)) {
                    found = false;
                    break;
                }
            }

            if (found) {
                // Match in the mddle
                if (j == m) return ans;
                    // Match second half of A
                else if (i + j == n) {
                    break;
                }
            }
            i++;
        }
        if (!found) return -1;
        i = 0;
        while (j < m) {
            if (A.charAt(i) != B.charAt(j)) {
                return -1;
            }
            if (i == 0) {
                ans++;
            }
            j++;
            i = (i + 1) % n;
        }
        return ans;
    }
}
